/*
 *https://leetcode.cn/problems/nearest-exit-from-entrance-in-maze/description/
 *lc1926. 迷宫中离入口最近的出口
 *medium 吴朝泽 2024.12.3
 *BFS广度优先搜索
*/

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    struct Node 
    {
        int x, y, s;  // x, y 坐标和当前的步数
    };

    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        int a = maze.size();
        int b = maze[0].size();
        int xx[] = {0, 1, 0, -1};  // 上下左右的移动方向
        int yy[] = {1, 0, -1, 0};
        
        queue<Node> q;
        q.push(Node{entrance[0], entrance[1], 0});
        
        // 标记访问过的地方，0 未访问，1 已访问
        bool vis[110][110] = {false};
        vis[entrance[0]][entrance[1]] = true;

        while (!q.empty()) {
            Node curr = q.front();
            q.pop();

            // 判断当前点是不是出口，注意不能是起点
            if ((curr.x != entrance[0] || curr.y != entrance[1]) &&
                (curr.x == 0 || curr.x == a - 1 || curr.y == 0 || curr.y == b - 1)) {
                return curr.s;
            }

            // 遍历四个方向
            for (int i = 0; i < 4; ++i) {
                int dx = curr.x + xx[i];
                int dy = curr.y + yy[i];

                // 检查新的位置是否合法且未访问过
                if (dx >= 0 && dx < a && dy >= 0 && dy < b && maze[dx][dy] == '.' && !vis[dx][dy]) {
                    vis[dx][dy] = true;
                    q.push(Node{dx, dy, curr.s + 1});
                }
            }
        }
        return -1;
    }
};
